package chapter02;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

public class GrayCode89 {
    /**
     * 镜像对称
     * 观察规律
     * n==1 0 1
     * n==2 00 01|11 10
     * n==3 000 001 011 010|110 111 101 100
     * n==m 数组中的数依据镜像从后向前遍历 将第m位取反即可
     * 初始化 0和1存入path 从第2位开始 循环将path中所有数依据镜像从后往前第m位数字取反即可
     * target->[2,n]
     *      for index->path:[length-1,0]
     *          path.add([index]|1<<(target-1))
     */
    public List<Integer> grayCode(int n) {
        List<Integer> path=new ArrayList<>();
        path.add(0);
        path.add(1);
        int target=2;
        while (target<=n){
            int length=path.size();
            for(int i=length-1;i>=0;i--){
                path.add((1<<(n-1))|path.get(i));
            }
            target++;
        }
        return path;
    }
}
